[Coding032] LeetCode 24

Swap Nodes in Pairs

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• 时隔多天又开始重整旗鼓，再次开始编程了，不知道这次又能坚持多久呢？

• 怕什么真理无穷，进一寸有一寸的欢喜！

题目：24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4]
2
Output: [2,1,4,3]

Example 2:

xxxxxxxxxx
2
1
Input: head = []
2
Output: []

Example 3:

xxxxxxxxxx
2
1
Input: head = [1]
2
Output: [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].

• 0 <= Node.val <= 100

代码1（配 · 手绘过程图）

xxxxxxxxxx
37
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode swapPairs(ListNode head) {
13
        ListNode dummy = new ListNode(0);
14
        ListNode res = dummy;
15
        ListNode p = head;
16

17
        if (p == null) return null;
18
        if (p.next == null) return p;
19

20
        // 连续判断当前节点和当前节点的下一个节点；
21
        while (p != null && p.next != null)
22
        {
23
            ListNode q = p.next;
24
            ListNode r = q.next;
25

26
            res.next = q;
27
            q.next = p;
28
            p.next = r;
29
            res = res.next.next;
30

31
            p = r;
32
        }
33

34
        return dummy.next;
35

36
    }
37
}

编写过程的感受记录

在写这道程序的时候，已经距离上次的coding时隔近2个月，有些手生。

我先是把既往关于链表的内容大概看了下，然后开始编写这道程序。虽然这是中等难度题，但是编起来也确实让我感触良多。一开始比较害怕写那个while循环，因为想到while循环里可能是需要判断2个条件，这个让我感觉有点不太正常，但是仔细分析之后，感觉还是需要这样写。不然没法往下写逻辑，索性我就试试看了。

然后在网页IDE的报错提示下，我渐渐完善，最后完成了100%的代码。很开心。

但是因为手边没有草稿纸和iPad，所以此刻（2024年3月22日 18:35:33）暂时先不发布，今天晚上或者明天再整理代码进行发布。

要大胆去写，错了又何妨呢？爱迪生说：“我不是失败了10000次，我只是发现了10000条行不通的路罢了。”

代码2（配 · 手绘过程图）

xxxxxxxxxx
38
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode swapPairs(ListNode head) {
13
        if (head == null || head.next == null)
14
            return head;
15
        
16
        ListNode dummy = new ListNode(0);
17

18
        dummy.next = head;
19
        
20
        ListNode cur = dummy;        
21
        ListNode p = cur.next;
22

23
        while(p != null && p.next != null)
24
        {                           
25
            ListNode q = p.next;
26
            
27
            p.next = q.next;
28
            q.next = cur.next;
29
            cur.next = q;
30

31
            
32
            cur = p;         
33
            p = cur.next;
34
        }
35
        
36
        return dummy.next;
37
    }
38
}

代码解读 | 评价

• 这个代码和上一个大同小异，上一个是我当天写的；这个代码是很久之前做的。

从这里也能看出来，算法真的很巧妙，不管你什么时候做，答案总是差不多。这就是算法的可复现性吧！

fighting！